import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/23 10:41
 * @description BFS，在一轮中，将所有设计到的点都扩散出去
 */
public class Solution2 {
    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        int[][] grid = {{0,1}, {1,0}};
        solution2.shortestPathBinaryMatrix(grid);
    }
    private int[][] dirs = {{1, 1}, {1, 0}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};

    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid[0][0] == 1) {
            return -1;
        }
        Arrays.sort(grid, (o1, o2) -> {
            if(o1[1] != o2[1]) {
                return o2[1] - o1[1];
            }else {
                return o1[0] - o2[0];
            }
        });
        int n = grid.length;
        boolean[][] visited = new boolean[n][n];
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{0,0});
        int ans = 1;
        while (!queue.isEmpty()) {
            int m = queue.size();
            while (m > 0) {
                int[] temp = queue.poll();
                int i = temp[0], j = temp[1];
                if (i == n - 1 && j == n - 1) {
                    return ans;
                }
                for (int k = 0; k < 8; k++) {
                    int ni = dirs[k][0] + i, nj = dirs[k][1] + j;
                    if (ni >= 0 && ni < n && nj >= 0 && nj < n && grid[ni][nj] == 0 && !visited[ni][nj]) {
                        visited[ni][nj] = true;
                        queue.add(new int[]{ni, nj});
                    }
                }
                m--;
            }
            ans++;
        }
        return -1;


    }

}
